﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution1 {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hash;//存储字典中的单词

        for (auto& s : wordDict) hash.insert(s);

        int n = s.size();
        vector<bool> dp(n + 1);//增设虚拟节点
        dp[0] = true;//虚拟节点需设为true
        s = ' ' + s; // 使原始字符串的下标统⼀ + 1

        for (int i = 1; i <= n; ++i)
        {
            for (int j = i; j >= 1; --j)
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

class Solution2 {
public:
    int findSubstringInWraproundString(string s) {
        int n = s.size();

        vector<int> dp(n, 1);
        int hash[26] = { 0 };//用于存储以每个字母为结尾的子串在dp表中的最大值,用于去重
        for (int i = 1; i < n; ++i)
        {
            if (s[i - 1] == s[i] - 1 || (s[i - 1] == 'z' && s[i] == 'a'))
                dp[i] += dp[i - 1];
        }

        for (int i = 0; i < n; ++i)
        {
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }

        int sum = 0;
        for (auto x : hash) sum += x;

        return sum;
    }
};

int main()
{
	return 0;
}